package com.laotang.第_17_章_动态规划.力扣_918_环形子数组的最大和;

/**
 * @官方网站 : https://douma.ke.qq.com
 * @微信公众号 : 抖码课堂
 * @官方微信号 : bigdatatang01
 * 抖码算法，让算法学习变的简单有趣
 * @作者 : 老汤
 */
public class _918_maximum_sum_circular_subarray {

    public int maxSubarraySumCircular(int[] nums) {
        // 1. 在原数组 nums 内求最大子数组和，参考 leetcode 53 号算法题：最大子序和
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int maxSum = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            maxSum = Math.max(maxSum, dp[i]);
        }

        // 如果最子数组和小于 0，说明数组中全为负数，返回最大负数即可
        if (maxSum < 0) return maxSum;

        // 2. 在原数组 nums 内求最小子数组和
        dp = new int[nums.length];
        dp[0] = nums[0];
        int minSum = dp[0];
        int sum = nums[0]; // 存储 nums 所有元素和
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.min(dp[i - 1] + nums[i], nums[i]);
            minSum = Math.min(minSum, dp[i]);
            sum += nums[i];
        }

        return Math.max(maxSum, sum - minSum);
    }
}
